#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#include <limits.h>
#include <sys/timeb.h>

#include <omp.h>
#include <mpi.h>

#include "preprocessor.h"
#include "avl.h"

#define ROOT 0
#define TIMEOUT 5

/* Ponteiro para o arquivo que contera os palavras encontradas */
FILE * pFile;

/* Estrutura que representa o comunicador universal */
MPI_Comm comm = MPI_COMM_WORLD;
/* Variavel que contém o status das operacoes que serao realizadas */
MPI_Status status;

/* Arvores primarias */
/* Arvore primaria que contem as palavras completas */
node * words = NULL;
/* Arvore primaria que contem de 0 a 5 letras */
node * words5 = NULL;
/* Arvore primaria que contem de 5 a 10 letras */
node * words10 = NULL;
/* Arvore primaria que contem de 10 a 15 letras */
node * words15 = NULL;
/* Arvore primaria que contem de 15 a 20 letras */
node * words20 = NULL;
/* Arvore primaria que contem de 20 e mais letras */
node * words25 = NULL;

/* Arvores secundarias */
/* Arvore secundaria que contem as palavras encontradas completas */
node * words2 = NULL;
/* Arvore secundaria que contem de 0 a 5 letras encontradas */
node * words2_5 = NULL;
/* Arvore secundaria que contem de 5 a 10 letras encontradas */
node * words2_10 = NULL;
/* Arvore secundaria que contem de 10 a 15 letras encontradas */
node * words2_15 = NULL;
/* Arvore secundaria que contem de 15 a 20 letras encontradas */
node * words2_20 = NULL;
/* Arvore secundaria que contem de 20 e mais letras encontradas */
node * words2_25 = NULL;

/* Variavel para calcular o tempo de execucao do programa */
double seconds;

/* Variavel necessaria para as funcoes de troca de mensagem da MPI */
int tag = 0;
/* Variavel que contem o valor do noh que enviou a mensagem */
int source;

/* Variavel contadora */
int i;
/* Variavel contadora */
int j;
/* Variavel que indica a quantidade encontrada nos nohs */
int counter_word_parcialTree = 0;
/* Contador das palavras do arquivo */
int counter_word_total = 0;
/* Contador das palavras encontradas */
int counter_word_parcial = 0;
/* Variavel que contera a palavra para comparacao */
int words_size[46] = {0};
/* Variavel que contem a quantidade de nos */
int size;
/* Variavel que contem o id do noh */
int id;
/* Variavel que contem os valores aleatorios */
int n;
/* Variavel que contem o valor da rotacao */
int w;
/* Variavel que contem o id da thread dentro do noh */
int th_id;
/* Variavel que indica a rotacao do alfabeto */
int flag = 0;
/* Variavel que representa a porcentagem atingida */
int percent = 0;
/* Variavel que representa se ocorreu um erro durante operacoes */
int error;
/* Variavel que avisa se aos nos para terminarem */
int finish = 0;
/* Variavel que indica o tamanho da palavra */
int len;
/* Valor total de palavras diferentes a serem encontradas */
int sum;

/* Variavel auxiliar que recebe a letra aleatoria */
char c;

/* Struct que representa o tempo antes de comecar */
struct timeb time_bef;
/* Struct que representa o tempo apos uma operacao */
struct timeb time_aft;

/* Funcao que sera executado no noh raiz */
void root();
/* Funcao que trata as arvores de 0 a 5 letras */
void tree();

int main(int argc, char * argv[])
{
    /* Inicializacao da MPI */
    error = MPI_Init(&argc, &argv);
    if(error != MPI_SUCCESS)
    {
        printf("Erro ao inicializar a MPI. Fechando o programa.\n");
        MPI_Finalize();
        exit(1);
    }

    /* Coletando informacoes das threads */
    MPI_Comm_size(comm, &size);
    MPI_Comm_rank(comm, &id);

    /* Devido as funcoes utilizadas, necessitamos de pelo menos 2 nos */
    if(size < 2)
    {
        printf("Para execução deve-se ter pelo menos 2 nós.\n");
        MPI_Finalize();
        exit(1);
    }

    /* Executa o preprocessamento do arquivo, criando as arvores primarias */
    words = preProcessor(&counter_word_total, words_size,
                         &words5, &words10, &words15, &words20, &words25);

    /* calcula o valor total de palavras diferentes */
    sum = getSizeTree(words5) + getSizeTree(words10) + getSizeTree(words15) +
        getSizeTree(words20) + getSizeTree(words25);

    /* Dependendo do id do noh, executa a respectiva funcao */
    if(id == ROOT)
        root();
    else if(id != ROOT)
        tree();

    /* Se for o noh raiz fecha o arquivo */
    if(id == ROOT)
    {
        fclose(pFile);
        ftime(&time_aft);
        /* Calcula-se os segundos passados desde a inicializacao do programa */
        seconds = (time_aft.time - time_bef.time) +
            (time_aft.millitm - time_bef.millitm) / 1000.0;
        printf("Tempo total: %.3f sec\n", seconds);
    }

    MPI_Finalize();
    return 0;
}

/* Funcao que sera executado no noh raiz */
void root()
{
    /* Abre o arquivo que contera as palavras finais */
    pFile = fopen("res_word_3.txt", "w");

    char s[50] = {0};

    /*Inicia o contador de tempo */
    ftime(&time_bef);
    /* Variavel para indicar quando os processos terminam */
    int k = size - 1;
    /*
     * Enquanto o contador parcial for menor que o contador total ou
     * todos os processos nao terminaram continua executando o bloco
     */
    while(counter_word_parcial < counter_word_total && k > 0)
    {
        /* Recebe o tamanho da palavra de algum noh */
        MPI_Recv(&len, 1, MPI_INT, MPI_ANY_SOURCE, tag, comm, &status);
        /*
         * Se o tamanho for -1, indica que o noh terminou o seu processamento,
         * decrementa o contador e espera todos os nos terminarem
         */
        if(len == -1)
            k--;
        else {
            /*
             * Recebe ah partir do noh que enviou o tamanho, a palavra e
             * a procura nas arvores primarias
             */
            source = status.MPI_SOURCE;
            MPI_Recv(&s, len, MPI_CHAR, source, tag, comm, &status);
            s[len] = '\0';

            node * aux;
            node * aux_tree;

            /*
             * Todos os blocos de if abaixo seguem a mesma ideia
             * portanto comentaremos o funcionamento do primeiro, que eh
             * equivalente para todos os outros nessa funcao
             */
            /* procura a palavra na arvore primaria de 0 a 5 letras */
            aux = find(s, words5);
            if(aux != NULL)
            {
                /* procura a palavra na arvore secundaria de 0 a 5 letras */
                if(find(s, words2_5) == NULL)
                {
                    /*
                     * se ela nao existir, insere-se na arvore secundaria
                     * para mantermos as palavras ja encontradas
                     */
                    words2_5 = insert(s, words2_5);
                    while(aux->rowSub)
                    {
                        /*
                         * Procuramos na lista e marcamos o bloco encontrado
                         * em todas as palavras maiores
                         */
                        aux_tree = findSub(getRowNode(aux), words, 0);
                        /* se foram encontrados todos os blocos imprimos no arquivo */
                        if(aux_tree->complete)
                        {
                            fprintf(pFile, "%s\n", aux_tree->word);
                            counter_word_parcial++;
                        }
                    }
                }
            }

            /* o mesmo que o anterior para a arvore de 5 a 10 letras */
            aux = find(s, words10);
            if(aux != NULL)
            {
                if(find(s, words2_10) == NULL)
                {
                    words2_10 = insert(s, words2_10);
                    while(aux->rowSub)
                    {
                        aux_tree = findSub(getRowNode(aux), words, 1);
                        if(aux_tree->complete)
                        {
                            fprintf(pFile, "%s\n", aux_tree->word);
                            counter_word_parcial++;
                        }
                    }
                }
            }

            /* o mesmo que o anterior para a arvore de 10 a 15 letras */
            aux = find(s, words15);
            if(aux != NULL)
            {
                if(find(s, words2_15) == NULL)
                {
                    words2_15 = insert(s, words2_15);
                    while(aux->rowSub)
                    {
                        aux_tree = findSub(getRowNode(aux), words, 2);
                        if(aux_tree->complete)
                        {
                            fprintf(pFile, "%s\n", aux_tree->word);
                            counter_word_parcial++;
                        }
                    }
                }
            }

            /* o mesmo que o anterior para a arvore de 15 a 20 letras */
            aux = find(s, words20);
            if(aux != NULL)
            {
                if(find(s, words2_20) == NULL)
                {
                    words2_20 = insert(s, words2_20);
                    while(aux->rowSub)
                    {
                        aux_tree = findSub(getRowNode(aux), words, 3);
                        if(aux_tree->complete)
                        {
                            fprintf(pFile, "%s\n", aux_tree->word);
                            counter_word_parcial++;
                        }
                    }
                }
            }

            /* o mesmo que o anterior para a arvore de 20 ou mais letras */
            aux = find(s, words25);
            if(aux != NULL)
            {
                if(find(s, words2_25) == NULL)
                {
                    words2_25 = insert(s, words2_25);
                    while(aux->rowSub)
                    {
                        aux_tree = findSub(getRowNode(aux), words, aux->blocks);
                        if(aux_tree->complete)
                        {
                            fprintf(pFile, "%s\n", aux_tree->word);
                            counter_word_parcial++;
                        }
                    }
                }
            }

            /*
             * Verifica se a porcentagem mudou e imprime o valor total de palavras,
             * o valor encontrado, a porcentagem e o tempo gasto
             */
            if (percent != (counter_word_parcial * 100) / counter_word_total)
            {
                percent = (counter_word_parcial * 100) / counter_word_total;
                ftime(&time_aft);
                seconds = (time_aft.time - time_bef.time) +
                    (time_aft.millitm - time_bef.millitm) / 1000.0;
                printf("%d %d %d %.3f\n", counter_word_total,
                        counter_word_parcial, percent, seconds);
            }
        }
    }
}

/* Funcao que trata as arvores de 0 a 5 letras */
void tree()
{
    #pragma omp parallel private(i,j) shared(counter_word_parcialTree)
    {
        /* Inicia-se a semente randomica com o id do processo */
        srand(id);
        n = rand();
        int l;
        node * aux_sub = NULL;

        /* Alfabeto que sera utilizado */
        char chars[27] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
                          'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
                          'u', 'v', 'w', 'x', 'y', 'z', '{'};
        int r;

        ftime(&time_bef);

        /* Enquanto o noh nao terminar, continua o processamento */
        while (finish == 0)
        {
            char s[50] = {0};

            /*
             * If destinado para a rotacao do alfabeto
             * tivemos que realizar a alteracao porque para os testes tinhamos
             * que usar a mesma semente, na versao original, a ideia eh usar
             * uma semente que se altera para rotacionarmos o alfabeto de forma
             * ainda mais aleatoria
             */
            if (flag > 100000)
            {
                flag = 0;
                r = rand() % 27;

                /*
                 * Executa a rotacao do alfabeto, similar ao que acontece
                 * na cifra de Cesar
                 */
                for (w = 0; w < 27; w++)
                    chars[w] = ((chars[w] - 'a') + r) % 27 + 'a';

            }

            /* loop que limita o tamanho da palavra a ser criada */
            for (i = 1; i <= 100; i++)
            {
                flag++;
                /* gera a palavra de tamanho i */
                for (j = 1; j <= i; j++)
                {
                    /* gera se a palavra aleatoria */
                    n = rand() % 27;
                    c = chars[n];
                    s[j - 1] = c;

                    if (findN(s, words, j) == NULL)
                        break;

                    /* calcula o tamanho da palavra */
                    l = strlen(s);

                    /*
                     * Todos os blocos de if abaixo seguem a mesma ideia
                     * portanto comentaremos o funcionamento do primeiro, que eh
                     * equivalente para todos os outros nessa funcao
                     */
                    /* se encontrou a palavra na arvore de 0 a 5 letras  */
                    #pragma omp critical
                    if ((aux_sub = find(s, words5)) != NULL)
                    {
                        /* procura-se pela mesma na arvore secundaria de 0 a 5 letras */
                        if (find(s, words2_5) == NULL)
                        {
                            /* reset a variavel de rotacao do alfabeto */
                            flag = 0;
                            /* insere-se a palavra na arvore secundaria */
                            words2_5 = insert(s, words2_5);

                            /* calcula-se o tempo depois */
                            ftime(&time_aft);
                            seconds = (time_aft.time - time_bef.time) +
                                (time_aft.millitm - time_bef.millitm) / 1000.0;
                            if(l > 0)
                            {
                                /* incrementa a quantidade de palavras encontradas */
                                counter_word_parcialTree++;
                                /* marca o tempo anterior */
                                ftime(&time_bef);
                                /* envia para a raiz o tamanho e a palavra encontrada */
                                MPI_Send(&l, 1, MPI_INT, ROOT, tag, comm);
                                MPI_Send(&s, l, MPI_CHAR, ROOT, tag, comm);
                            }
                        }
                    }

                    /* o mesmo que o anterior para a arvore de 5 a 10 letras */
                    #pragma omp critical
                    if ((aux_sub = find(s, words10)) != NULL)
                    {
                        if (find(s, words2_10) == NULL)
                        {
                            flag = 0;
                            words2_10 = insert(s, words2_10);

                            ftime(&time_aft);
                            seconds = (time_aft.time - time_bef.time) +
                                (time_aft.millitm - time_bef.millitm) / 1000.0;
                            if(l > 0)
                            {
                                counter_word_parcialTree++;
                                ftime(&time_bef);
                                MPI_Send(&l, 1, MPI_INT, ROOT, tag, comm);
                                MPI_Send(&s, l, MPI_CHAR, ROOT, tag, comm);
                            }
                        }
                    }

                    /* o mesmo que o anterior para a arvore de 10 a 15 letras */
                    #pragma omp critical
                    if ((aux_sub = find(s, words15)) != NULL)
                    {
                        if (find(s, words2_15) == NULL)
                        {
                            flag = 0;
                            words2_15 = insert(s, words2_15);

                            ftime(&time_aft);
                            seconds = (time_aft.time - time_bef.time) +
                                (time_aft.millitm - time_bef.millitm) / 1000.0;
                            if(l > 0)
                            {
                                counter_word_parcialTree++;
                                ftime(&time_bef);
                                MPI_Send(&l, 1, MPI_INT, ROOT, tag, comm);
                                MPI_Send(&s, l, MPI_CHAR, ROOT, tag, comm);
                            }
                        }
                    }

                    /* o mesmo que o anterior para a arvore de 15 a 20 letras */
                    #pragma omp critical
                    if ((aux_sub = find(s, words20)) != NULL)
                    {
                        if (find(s, words2_20) == NULL)
                        {
                            flag = 0;
                            words2_20 = insert(s, words2_20);

                            ftime(&time_aft);
                            seconds = (time_aft.time - time_bef.time) +
                                (time_aft.millitm - time_bef.millitm) / 1000.0;
                            if(l > 0)
                            {
                                counter_word_parcialTree++;
                                ftime(&time_bef);
                                MPI_Send(&l, 1, MPI_INT, ROOT, tag, comm);
                                MPI_Send(&s, l, MPI_CHAR, ROOT, tag, comm);
                            }
                        }
                    }

                    /* o mesmo que o anterior para a arvore de 20 ou mais letras */
                    #pragma omp critical
                    if ((aux_sub = find(s, words25)) != NULL)
                    {
                        if (find(s, words2_25) == NULL)
                        {
                            flag = 0;
                            words2_25 = insert(s, words2_25);

                            ftime(&time_aft);
                            seconds = (time_aft.time - time_bef.time) +
                                (time_aft.millitm - time_bef.millitm) / 1000.0;
                            if(l > 0)
                            {
                                counter_word_parcialTree++;
                                ftime(&time_bef);
                                MPI_Send(&l, 1, MPI_INT, ROOT, tag, comm);
                                MPI_Send(&s, l, MPI_CHAR, ROOT, tag, comm);
                            }
                        }
                    }

                    /*
                     * Se atingimos o valor esperado de palavras ou se houve timeout
                     * terminamos o processamento no noh
                     */
                    #pragma omp critical
                    if(sum <= counter_word_parcialTree || seconds > TIMEOUT){
                        finish = 1;
                        j = 102;
                        i = 101;
                        /* envia para a raiz o tamanho -1 como sinal de que terminou */
                        l = -1;
                        MPI_Send(&l, 1, MPI_INT, ROOT, tag, comm);
                    }
                }
            }
        }
    }
}
